1. Field of the Invention
The present invention relates to expressive auctions for the allocation of differentiated supply. The invention will be described in connection with advertising auctions, i.e., auctions for the display of advertisements on computer devices, but applies more broadly to the allocation of differentiated supply of any collection of goods (e.g., to bidders or participants in a marketplace).
2. Description of Related Art
Online advertising has radically changed both the nature of advertising and the technology used to support the development and deployment of ad campaigns. While ad targeting and campaign design is inherently complex, the variety of online advertising services has only increased this complexity. In particular, the ability to target ads to specific individuals based on detailed, personalized online information—information that is simply not available in broadcast media—presents compelling opportunities and tremendous technical challenges for ad delivery. For instance, the development of sophisticated matching and bidding algorithms for sponsored search, such as position auctions using the generalized second price (GSP) mechanism, can be viewed as a response to such opportunities.
Contextual information about a user that suggests what a user is looking for and thinking about when engaged in online activities (such as web search) is extremely valuable to advertisers. The ability to target their advertisements to those users where the likelihood of impact is greatest—as suggested by the current contextual information—can dramatically improve the effectiveness of ads. The publishers of online information and providers of online services (such as search engines) have access to valuable contextual cues that can be used to help target advertisements.
This current state of online advertising can be characterized roughly as follows: Potential advertisers can interact directly with a publisher or search engine to determine where (and when) to place their ads, or they can reach a wide set of publishers by placing their ads via an advertising network. Generally, an advertiser will indicate the contextual conditions of interest, the amount they are willing to pay for placement of their ad or for some event caused by the ad placement (such as a click on their ad)—assuming the contextual conditions are met—and often a budget limiting the total amount of spend (and, indirectly, the number of ads placed).
One example of this interaction is exemplified by the Google search engine. An advertiser indicates their interest in specific users by bidding on particular query keywords, with their bid indicating a maximal willingness-to-pay per click for different keyword queries. For instance, “I will pay $0.10 for each query with search terms basketball+betting but no more than $200 each 24 hours”. Advertisers (bidders) compete for the right to display ads, and the price paid per click for any winning bidder is a function of the other bids competing for the same (or related) keywords. In other words, Google, like many other search engines, publishers, and ad networks, uses an auction to place ads.
Another example is the display of banner ads through an advertising network. The network (e.g., as exemplified by RightMedia) consists of potential advertisers and publishers of web content/services. Advertisers bid for the right to display ads on particular types of web sites/pages, while publishers can restrict the types of ads that can appear on their sites. Again, an auction is typically used to determine a suitable assignment of ads to specific web sites/pages. Advertisers can indicate their target users of interest by specifying appropriate contextual conditions. For instance, the advertiser might specify that their ad must only be displayed: on web pages with a particular type of content (e.g., as indicated by the presence of keywords, tags, etc.); at a certain time of day; to users with a particular demographic profile (e.g., as verified by publishers of subscription sites/services, or estimated by the publisher).
More general expressive advertising auctions allow advertisers to express extremely complex conditions on the placement of their ads. In expressive auctions, advertisers can express their willingness to pay for sequences or sets of ad impressions, clicks, or other events. Expressiveness forms include: payment only if minimum targets are met; multiple targets and tiered payment; temporal sequencing of different ads; substitution of different web sites or other contextual properties.
It is important to realize that the supply of advertising space to advertisers need not be determined by an auction or an explicit market mechanism. It could be allocated using non-competitive processes such manually negotiated contracts between publishers/ad networks and advertisers. However, advertisers are rarely interested in arbitrary placement of ads: even in non-market based settings, the contextual information associated with an ad placement is vital.
In contrast to sponsored search, the selling of banner ads (aka. display ads) is still largely approached through manual negotiation. There are some exceptions to this, with online exchanges for banner ads established by companies like Right Media (now part of Yahoo!) and DoubleClick (now part of Google); however, these exchanges largely deal with lower-value, “remnant” inventory on web sites. Premium display advertising space (e.g., slots near the top, or “above the fold”, of high traffic, high profile websites) is sold almost exclusively by non-automated means. The primary reason for this is a perception that auction/market mechanisms cannot be made to work for the types of campaign-level expressiveness required for display ads (e.g., as required by brand advertisers). This parallels the situation is sourcing, where advances in modeling and optimization have led to the adoption of expressive bidding (and expressive bid-taking) for what had previously been widely viewed as “too valuable” to leave to auction mechanisms. The expressive auction mechanisms are now used also for striking strategic long-term contracts on the most valuable parts of the sourcing spend.
In campaign-level-expressiveness, a variety of expressiveness forms are outlined (these include impression targets, smoothness of delivery, temporal sequencing, complements and substitutes, and many others). Although sophisticated bidding strategies can be effective in optimizing some limited forms of expressive preferences (e.g., long-term budgets) in an inexpressive auction, arbitrarily large inefficiencies can nevertheless arise. Allowing richer languages in which advertisers can express their campaign preferences directly, rather than forcing them into standard per-impression or per-click bidding models, is critical to admitting the automated matching and selling of banner ads.
A key bottleneck remains: the use of expressive bidding requires optimization to match ad supply with advertisers' demand. The richer the expressiveness forms, the more complex the optimization. For example, a stochastic optimization model can allocate ad supply to advertisers who bid using rich, campaign-level expressiveness forms. It can explicitly account for uncertainty in both supply and demand. However, it has long been recognized that even with very limited forms of expressiveness—as simple as per-impression value/pricing with budget constraints and bid expiration—that optimization is critical to extracting full value from one's ad inventory. Indeed, using simple myopic mechanisms like GSP can lead to significant loss in efficiency and revenue.